#pragma once

#include <vector>

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode() : val(0), left(nullptr), right(nullptr) { }
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) { }
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) { }
};

class Solution
{
public:
    std::vector<int> preorderTraversal(TreeNode* root)
    {
        std::vector<int> visited;
        traverse_preorder(root, visited);
        return visited;
    }

    std::vector<int> preorderTraversal2(TreeNode* root)
    {
        std::vector<int> visited;
        if (root == nullptr)
            return visited;

        std::vector<TreeNode*> stack;
        stack.push_back(root);

        while (!stack.empty()) {
            auto node = stack.back();
            visited.push_back(node->val);
            stack.pop_back();

            if (node->right) stack.push_back(node->right);
            if (node->left)  stack.push_back(node->left);
        }

        return visited;
    }

private:
    void traverse_preorder(TreeNode* root, std::vector<int>& visited)
    {
        if (root == nullptr)
            return;
        visited.push_back(root->val);
        traverse_preorder(root->left, visited);
        traverse_preorder(root->right, visited);
    }
};
